package com.example.demo.algorithm.binarysearch;

/**
 * 二分查找法
 */
public class BinarySearch {

    private BinarySearch() {
    }

    /**
     * 递归方式
     *
     * @param <E>
     * @return
     */
    public static <E extends Comparable<E>> int search(E[] data, E target) {

        return binarySearch(data, 0, data.length - 1, target);
    }

    /**
     * 递归逻辑
     *
     * @param data
     * @param l      左边界
     * @param r      右边界
     * @param target
     * @param <E>
     * @return
     */
    private static <E extends Comparable<E>> int binarySearch(E[] data, int l, int r, E target) {
        //解决问题释放内存
        //索引大于r说明没有找到
        if (l > r) {
            return -1;
        }
        //找到该数组的中间部分
        int mid = l + (r - l) / 2;
        //如果中间值是要查找的说明找到了返回该索引
        if (data[mid].compareTo(target) == 0) {
            return mid;
        }
        //中间的mid不需要扫描 因为已经找到了
        //如果中间值小于要查找的继续找右边
        if (data[mid].compareTo(target) < 0) {
            //右边  解释 mid+1就是从右边开始到r为边界 如果数组是50 由于最后一个数是长度 -1  那么也就是 24 + 1 = 25开始找
            return binarySearch(data, mid + 1, r, target);
        }
        //中间的mid不需要扫描 因为已经找到了
        //如果中间值小于要查找的继续找左边
        //左边 解释 mid+1就是从左边l索引0开始到 中间mid为边界 如果数组是50 由于最后一个数是长度 -1  那么也就是 25 - 1 = 24开始找
        return binarySearch(data, l, mid - 1, target);
    }

    /**
     * 非递归方式 前闭后闭 [l r]
     *
     * @param <E>
     * @return
     */
    public static <E extends Comparable<E>> int searchR(E[] data, E target) {
        int l = 0, r = data.length - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (data[mid].compareTo(target) == 0) {
                return mid;
            }
            if (data[mid].compareTo(target) < 0) {
                l = mid + 1;
            } else if (data[mid].compareTo(target) > 0) {
                r = mid - 1;
            }
        }
        return -1;
    }
    /**
     * 非递归方式 前闭后开 [l r)
     *
     * @param <E>
     * @return
     */
    public static <E extends Comparable<E>> int searchS(E[] data, E target) {
        int l = 0, r = data.length;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (data[mid].compareTo(target) == 0) {
                return mid;
            }
            if (data[mid].compareTo(target) < 0) {
                l = mid + 1;
            } else if (data[mid].compareTo(target) > 0) {
                r = mid;
            }
        }
        return -1;
    }
    public static void main(String[] args) {

        Integer[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        BinarySearch.search(arr, 7);
    }
}

